#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int res = 1, n = nums.size();
    vector<int> f(n + 1, 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (nums[i - 1] > nums[j - 1])
            {
                f[i] = max(f[i], f[j] + 1);
                res = max(res, f[i]);
            }
    return res;
}

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int INF = 0x3f3f3f3f;
    int dp[210][210] = { 0 };
    for (int i = 0; i <= n; i++) dp[0][i] = INF;
    for (int i = 2; i <= m; i++) dp[i][0] = INF;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }
    return dp[m][n];
}